1.绝对值不等式的本质(1.2.5)
2.德·摩根律在无穷情况下的推广(1.2.12)
3.施罗德-伯恩斯坦双射定理(1.4.13)
4.二维可数集的构造(1.4.8)
附录：$f$ 的通项公式

实数

习题 1.2 预备知识

(a) 使用反证的方式。假设存在互素整数 $p,q$ 满足 $p/q=\sqrt{3}$，那么 $p^2=3q^2$，$p$ 是 $3$ 的倍数，因此 $q$ 也是 $3$ 的倍数，这与 $p,q$ 互素的假设矛盾。所以 $\sqrt{3}$ 是无理数。

$\sqrt{6}$ 可以用同样的方式证明。

(b) 使用同样的方式，得到 $p^2=4q^2$，但此时只能得到 $p$ 是 $2$ 的倍数，于是可得到 $q=1$，这样不会产生矛盾。

(a) 这是可能不正确的。例如定义

$$A_n=\left\{x\in \mathbb{N}:x\geq n\right\}$$

则有

$$\displaystyle\bigcap_{n=1}^{\infty}{A_n}=\varnothing$$

(b) 这是正确的。证明它的关键是找到一个元素 $x$ 使 $x\in \displaystyle\bigcap_{n=1}^{\infty}{A_n}$。

尝试从有限非空的定义入手。与 (a) 问的区别在于，本题中 $A_{n+1}$ 的元素个数总是不大于 $A_n$ 的元素个数的。所以，从限制元素个数的角度入手，对某一 $k\in \mathbb{Z^+}$，

$$A_k=\left\{x_1,x_2,...,x_p\right\}$$

不妨设 $\exists \ n\in \mathbb{Z^+}$ 使 $\forall\ i\in \left\{1,2,...,p\right\}$ 都有 $x_i\notin A_n$，此时 $A_n\subseteq A_k$， 所以 $A_n=\varnothing$，这与其非空的事实矛盾。所以对 $\forall\ n\in \mathbb{Z^+}$ 都 $\exists \ i\in \left\{1,2,...,p\right\}$ 使得 $x_i\in A_n$，这就证明了 $\displaystyle\bigcap_{n=1}^{\infty}{A_n}$ 的非空性，又有限集合的交集是有限的，故它是有限非空的。

(c) 错误的。事实上左侧表达的是 $x\in A\cap B$ 或 $x\in A\cap C$，右侧表达的是 $x\in A\cap B$ 或 $x\in C$, 左侧是右侧的子集。

(d) 正确的。两者的元素都是同时属于三集合的元素。

(e) 正确的。

(a) 若 $x\in \left(A\cap B\right)^c$，则 $x\notin A$ 或 $x\notin B$，在 $x\in \mathbb{R}$ 的情况下，$x\in A^c$ 或 $x\in B^c$，即 $x\in A^c\cup B^c$，这说明 $\left(A\cap B\right)^c\subseteq A^c\cup B^c$。

(b) 同上反推，这样就能得到 $\left(A\cap B\right)^c= A^c\cup B^c$。

(c) 同理。

(a) 当 $a,b\geq 0$ 时，$|a|=a$，$|b|=b$，因此 $|a+b|\leq|a|+|b|$ 显然成立。

当 $a,b<0$ 时，$|a|=-a$，$|b|=-b$，所以原式可化作 $-(a+b)\leq-(a+b)$，仍然成立。

(b) $a\geq 0$，$b<0$，$a+b\geq 0$ 时，$|a|=a$，$|b|=-b$，$|a+b|=a+b<a-b=|a|+|b|$。

(a) 将 $b$ 替换成 $-b$，因为 $|-b|=|b|$，所以 $|a-b|\leq |a|+|-b|=|a|+|b|$。

(b) 绝对值不等式的本质

这里证明不等式的关键是，$|a+b|\leq|a|+|b|$ 这个不等式左右绝对值内的数字之和是一致的，要证不等式只要满足这个形式，通过赋值就能证明。

要证 $\left||a|-|b|\right|\leq|a-b|$, 其实是证明 $|a|-|b|\leq|a-b|$ 和 $|b|-|a|\leq|a-b|$，它们变形后为 $|a|\leq|a-b|+|b|$ 和 $|b|\leq |b-a|+|a|$，都满足前述绝对值不等式的形式。将绝对值不等式里的 $a$ 替换成 $a-b$ 或者是将 $b$ 替换成 $b-a$，就能证明。

(a) $f(A)=[0,4]$，$f(B)=[1,16]$，$A\cap B=[1,2]$，$A\cup B=[0,4]$，$f(A\cap B)=[1,4]$，$f(A)\cap f(B)=[1,4]$，$f(A\cup B)=[0,16]=f(A)\cup f(B)$。

(b) 由于 $f(x)=x^2$ 在不同的自变量取值下能得到相同的函数值，所以没有交集的集合它们的函数值是可能有交集的。例如取 $A=[-2,-1]$，$B=[1,2]$，$A\cap B=\varnothing$，$f(A\cap B)=\varnothing$，$f(A)\cap f(B)=[1,4]$，$f(A\cap B)\neq f(A)\cap f(B)$。

(c) 由这一映射的定义，对 $x\notin A$，$g(x)\in g(A)$ 的情形， $\exists\ x_1\in A$，$g(x_1)=g(x)$。所以对于这个问题，只需讨论 $A\cup B$ 中的 $x$ 即可。

由定义，$A\cap B$ 中的全体 $x$ 所对应的 $g(x)$ 组成 $g(A\cap B)$，$A$ 中的全体 $x$ 所对应的 $g(x)$ 组成 $g(A)$，$B$ 中的全体 $x$ 所对应的 $g(x)$ 组成 $g(B)$。所以 $g(A\cap B)\subseteq g(A)$ 且 $g(A\cap B)\subseteq g(B)$，从而 $g(A\cap B)\subseteq g(A)\cap g(B)$。

顺带附加说明这个式子在相反方向是不成立的。由 (b) 问的灵感，令 $x_1\in A\setminus B$，$x_2\in B$，若 $g(x_1)=g(x_2)$，由于 $g(x_1)\in g(A)$，$g(x_2)\in g(B)$，此时可得 $g(x_1)\notin g(A\cap B)$ 但是 $g(x_1)\in g(A)\cap g(B)$，所以 $g(A\cap B)\not\subseteq g(A)\cap g(B)$。

(d) $g(A\cup B)=g(A)\cup g(B)$。

同 (c) 问，只需考虑 $A\cup B$ 中的元素即可。令 $x\in A\cup B$，若 $x\in A$，则 $g(x)\in g(A)$，所以 $g(x)\in g(A)\cup g(B)$；若 $x\in B$，同理可得 $g(x)\in g(A)\cup g(B)$。所以 $g(A\cup B)\subseteq g(A)\cup g(B)$。

对于相反方向的情况，若 $g(x)\in g(A)\cup g(B)$，则 $g(x)$ 必定来自于 $g(A)$ 或 $g(B)$，所以 $x$ 必定来自于 $A\cup B$，这就证明了 $g(A)\cup g(B)\subseteq g(A\cup B)$。

所以 $g(A\cup B)=g(A)\cup g(B)$。

(a) $A\cap B=[0,1]$，$A\cup B=[-1,4]$。$f^{-1}(A)=[-2,2]$，$f^{-1}(B)=[-1,1]$，$f^{-1}(A\cap B)=[-1,1]$，$f^{-1}(A\cup B)=[-2,2]$。

所以 $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$，$(1)$

$f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)$。$(2)$

(b) 我们要证明对任意的 $g:\mathbb{R}\to \mathbb{R}$, 公式 $(1)$ 和 $(2)$ 仍然成立。

对于 $(1)$,我们有:

$x\in g^{-1}(A\cap B) \iff g(x)\in A\cap B \iff g(x)\in A \text{ 且 } g(x)\in B \iff x\in g^{-1}(A) \text{ 且 } x\in g^{-1}(B) \iff x\in g^{-1}(A)\cap g^{-1}(B)$

所以 $g^{-1}(A\cap B)=g^{-1}(A)\cap g^{-1}(B)$。

同理可得 $g^{-1}(A\cup B)=g^{-1}(A)\cup g^{-1}(B)$。

顺带说明此题和 $1.2.6.$ 结论的区别。事实上这关乎映射的单射性质。$x\mapsto f(x)$ 不一定是一个单射，而 $f(x)\mapsto x$ 一定是一个单射。 事实上，如果是一个单射，那么上述的两个公式将会成立。证明如下：

如果 $f$ 是一个单射，那么对于 $\forall\ x\notin A$，$f(x)\notin f(A)$。 从而 $f(x)\in f(A)\iff x\in A$。所以 $f(x)\in f(A\cap B)\iff x\in A\cap B\iff f(x)\in f(A)\cap f(B)$。$f(x)\in f(A\cup B)\iff x\in A\cup B\iff f(x)\in f(A)\cup f(B)$。

所以有 $f(A\cap B)=f(A)\cap f(B)$，$f(A\cup B)=f(A)\cup f(B)$。

(a) 存在两个实数 $a<b$，对任意 $n\in \mathbb{N}$，$a+1/n\geq b$。

(b) 存在两个实数，它们中间没有有理数。

(c) 存在 $n\in \mathbb{N}$，$\sqrt{n}$ 既不是自然数，也不是无理数。

(d) 存在 $x\in \mathbb{R}$，对 $\forall\ n\in \mathbb{N}$，$n\leq x$。

使用数学归纳法进行证明。假设 $x_n\leq 2$，则 $x_{n+1}=(1/2)x_n+1\leq 2$。

又因为 $x_1=1\leq 2$，所以对任意 $n\in \mathbb{N}$，都有 $x_n\leq 2$。

(a) 同上，假设 $y_n<4$，则 $y_{n+1}=(3y_n+4)/4<4$。又 $y_1=1$，故成立。

(b) 假设 $y_{n+1}>y_n$，则 $y_{n+2}-y_{n+1}=(3y_{n+1}+4)/4-(3y_n+4)/4=3(y_{n+1}-y_n)/4>0$，所以 $y_{n+2}>y_{n+1}$。

又因为 $y_2=7/4>y_1$，所以 $y_n$ 是递增的。

任何一个元素在子集中都有存在/不存在的两种可能性，所以有 $2^n$ 个子集。

(a) 若 $\left(A_1\cup A_2\cup \cdots \cup A_n\right)^c=A_1^c\cap A_2^c\cap \cdots \cap A_n^c$，则有 $\left(A_1\cup A_2\cup \cdots \cup A_n\cup A_{n+1}\right)^c=\left(A_1\cup A_2\cup \cdots \cup A_n\right)^c\cap A_{n+1}^c=A_1^c\cap A_2^c\cap \cdots \cap A_n^c\cap A_{n+1}^c$。又由于 $n=2$ 时是成立的，所以对任意 $n\in \mathbb{Z^+}$ 都成立。

(b) 因为有限是不能直接推广到无限的。

(c) 德·摩根律在无穷情况下的推广

$$\left(\displaystyle\bigcup_{n=1}^{\infty}A_n\right)^c=\displaystyle\bigcap_{n=1}^{\infty}A_n^c$$

是成立的。

设 $x\in (\displaystyle\bigcup_{n=1}^{\infty}A_n)^c$，则对 $\forall\ n\in \mathbb{N}$，$x\notin A_n$，即 $x\in A_n^c$，所以 $x\in \displaystyle\bigcap_{n=1}^{\infty}A_n^c$。这说明 $(\displaystyle\bigcup_{n=1}^{\infty}A_n)^c\subseteq \displaystyle\bigcap_{n=1}^{\infty}A_n^c$。

反之，设 $x\in \displaystyle\bigcap_{n=1}^{\infty}A_n^c$，则对 $\forall\ n\in \mathbb{N}$，$x\in A_n^c$，即 $x\notin A_n$，所以 $x\notin \displaystyle\bigcup_{n=1}^{\infty}A_n$，$x\in (\displaystyle\bigcup_{n=1}^{\infty}A_n)^c$ 。这说明 $\displaystyle\bigcap_{n=1}^{\infty}A_n^c\subseteq \left(\displaystyle\bigcup_{n=1}^{\infty}A_n\right)^c$。

综上所述，$\left(\displaystyle\bigcup_{n=1}^{\infty}A_n\right)^c=\displaystyle\bigcap_{n=1}^{\infty}A_n^c$。

参考资料：MSE上的证明

---

习题 1.3 完备性公理

(a)(b) 显然。

(c) 加法逆元均存在，乘法逆元里 $1,3$为其本身，$2$ 不存在。

$n\in \mathbb{Z^+}$ 时 $\mathbb{Z_n}$ 均存在加法逆元；$n$ 为质数时 $\mathbb{Z_n}$ 均存在乘法逆元。

(a) 称实数 $s$ 是集合 $A\subseteq \mathbb{R}$ 的最大下界， 若满足以下条件：

(i) $s$ 是 $A$ 的下界；

(ii) 若 $b$ 是 $A$ 的任一下界，则 $b\leq s$。

(b) 设 $s$ 是 $A\subseteq \mathbb{R}$ 的一个下界，则 $s=\inf A$ 当且仅当对 $\forall\ \varepsilon>0$，$\exists\ a\in A$，$s+\varepsilon>a$。

(a) 首先，对 $\forall\ a\in A$，$\forall\ b\in B$，有 $b\leq a$，所以集合 $B$ 存在上界，由完备性公理，其存在上确界 $\sup B$。下证 $\sup B=\inf A$。

(i) 若 $a<\sup B$，则 $\exists\ b \in B$，$a<b$，即 $a\notin A$。所以若 $a\in A$，$\sup B\leq a$，这说明 $\sup B$ 是 $A$ 的下界。

(ii) 又对 $\forall\ b\in B$，$b\leq \sup B$，所以 $\sup B$ 是$A$ 的最大下界，由定义，$\sup B=\inf A$。

(b) 完备性公理不需定义最大下界，直接定义下界的上确界即可。

(c) 设集合 $A$ 有下界，即存在 $Q\in \mathbb{R}$ 使得对 $\forall\ a\in A$，$Q\leq a$。要证明它有最大下界，我们从上界入手，试着把它的下界转换成上界。

设 $B=\left\{x\in \mathbb{R}:-x\in A\right\}$，那么对 $\forall\ x\in B$，有 $-x\in A$，所以 $-x\geq Q$，即 $x\leq -Q$，这说明 $B$ 有上界 $-Q$。由完备性公理，$B$ 有上确界 $\sup B$。

(i) 对 $\forall\ x\in B$，$x\leq \sup B$，即 $-x\geq -\sup B$；

(ii) 对 $\forall\ \varepsilon>0$，$\exists\ x\in B$ 使得 $\sup B-\varepsilon<x$，即 $-x<-\sup B+\varepsilon$。

因为 $\forall\ -x\in A$，$\exists\ x\in B$，所以上述两条性质对全体 $a\in A$ 都成立，所以 $A$ 的下确界存在，且 $\inf A=-\sup B$。

由题意，$\sup A$，$\sup B$ 均存在。

因为 $B\subseteq A$，所以对 $\forall\ b\in B$，$b\in A$，即 $b\leq \sup A$，这说明 $\sup A$ 是 $B$ 的一个上界，由 $\sup B$ 的定义，$\sup B\leq \sup A$。

由题意，$\sup A$ 存在。

(a) (i) 对 $\forall\ a\in A$，$a\leq \sup A$。所以对 $\forall\ x\in c+A$，$\exists\ a\in A$，使得 $x=c+a\leq c+\sup A$，所以 $c+\sup A$ 是 $c+A$ 的一个上界。

(ii) 对 $\forall\ \varepsilon>0$，$\exists\ a\in A$ 使得 $\sup A-\varepsilon<a$，所以 $\exists\ x\in c+A$ 使得 $x=c+a>c+\sup A-\varepsilon$。

所以 $\sup (c+A)=c+\sup A$。

(b) $c=0$ 时，$\sup (cA)=0=c\sup A$，显然成立。

$c>0$ 时，(i) 对 $\forall\ x\in cA$，$\exists\ a\in A$，使得 $x=ca\leq c\sup A$，所以 $c\sup A$ 是 $cA$ 的一个上界。

(ii) 对 $\forall\ \varepsilon>0$，$\exists\ a\in A$ 使得 $\sup A-\varepsilon<a$，所以 $\exists\ x\in cA$ 使得 $x=ca>c\sup A-c\varepsilon$,由 $\varepsilon$ 的任意性，得证。

所以 $\sup (cA)=c\sup A$。

(c) $c<0$ 时，$\sup (cA)=c\inf A$。通过改变不等号方向即可证明。

(a) 上确界 $3$，下确界 $1$。

(b) $1$，$0$。

(c) $1/2$，$1/3$。

(d) $9$，$1/9$。

对任何一个上界 $b$，因为 $a\in A$，所以 $a\leq b$，这说明 $a=\sup A$。

取 $\varepsilon=(\sup B-\sup A)/2$，则 $\exists\ b\in B$，$b>\sup B-\varepsilon=(\sup B+\sup A)/2>\sup A$，所以 $b$ 是 $A$ 的一个上界。

(a) 真。

(b) 假。考虑 $A=\left\{x\in \mathbb{Q}: x^2<2\right\}$，其内的任意元素都小于 $\sqrt{2}$，但是 $\sup A=\sqrt{2}$。

(c) 假。 考虑 (b) 中的 $A$ 和 $B=\left\{x\in \mathbb{Q}: x^2>2,x>0\right\}$，则对 $\forall\ a\in A,b\in B$ 有 $a<b$，但是 $\sup A=\inf B=\sqrt{2}$。

(d) 真。

(e) 假。考虑 (b) 中的 $A$，令 $B=A$，则 $\sup B=\sup A$，此时不存在 $b\in B$，使得 $b\geq \sup A$。

---

习题 1.4 完备性的推论

$a<0<b$ 时，$0$ 即为答案。

$a<b\leq 0$ 时，化成 $0\leq -b<-a$ 即可转化为前述情况证明。

(a) 由于 $a,b\in \mathbb{Q}$，那么可令 $a=p_1/q_1$，$b=p_2/q_2$，那么 $a+b=(p_1q_2+p_2q_1)/q_1q_2\in \mathbb{Q}$，同理 $ab\in \mathbb{Q}$。

(b) 由 $(a)$，若 $a+t\in \mathbb{Q}$，则 $t=(a+t)-a\in \mathbb{Q}$，所以 $a+t\in \mathbb{R}\backslash\mathbb{Q}$，同理 $at\in \mathbb{R}\backslash\mathbb{Q}$。

(c) $\mathbb{R}\backslash \mathbb{Q}$ 在加法和乘法下不封闭，更精确地说，无理数的运算结果可能是有理数。

任意两个实数 $a,b$ 之中必有一个有理数 $q$，使得 $a<q<b$。

所以 $a-\sqrt{2}<q-\sqrt{2}<b-\sqrt{2}$，由 $1.4.2.$ 可知 $q-\sqrt{2}$ 是无理数。

首先，对于 $\forall\ n\in \mathbb{Z^+}$，有 $0<1/n$，所以 $0$ 是 $\{1/n:n\in \mathbb{Z^+}\}$ 的一个下界。

下面证明 $0$ 是下确界。事实上由实数的阿基米德性，对 $\forall\ y>0$，$\exists\ n\in \mathbb{Z^+}$，$1/n<y$，所以任何比 $0$ 大的数都不是下界，即 $0$ 是下确界。

由阿基米德性的结论即可知对 $\forall\ y>0$，$y\notin \displaystyle\bigcap_{n=1}^{\infty} (0,1/n)$。所以 $\displaystyle\bigcap_{n=1}^{\infty} (0,1/n)=\varnothing$。

(a) 若 $\alpha^2>2$，对 $n\in \mathbb{N}^+$，取 $(\alpha-1/n)^2=\alpha^2-2\alpha/n+1/n^2>\alpha^2-2\alpha/n>2$，得 $n>2\alpha/(\alpha^2-2)$，所以 $\alpha-1/n$ 也是 $T$ 的上界，矛盾。

这里默认了 $\alpha>0$。

(b) $b=0$ 时是显然成立的。

$b>0$ 时，考虑集合 $T=\{t>0:t^2<b\}$。$b<1$ 时，$b\in T$ 且 $1$ 是 $T$ 的上界，所以 $\sup T$ 存在。$b\geq 1$ 同理可得其存在性。

令 $x=\sup T$，下面证明 $x^2=b$。

(i) 若 $x^2<b$，对 $n\in \mathbb{N}^+$，取 $(x+1/n)^2=x^2+2x/n+1/n^2<x^2+(2x+1)/n<b$，得 $n>(2x+1)/(b-x^2)$，即 $x+1/n$ 可能属于 $T$，矛盾。

(ii) 若 $x^2>b$，对 $n\in \mathbb{N}^+$，取 $(x-1/n)^2=x^2-2x/n+1/n^2>x^2-2x/n>b$，得 $n>2x/(x^2-b)$，即 $x-1/n$ 是 $T$ 的上界，矛盾。

所以 $x^2=b$。即 $x=\sqrt{b}$。

设 $n_2=\min \{n\in \mathbb{N}^+:f(n)\in A,n>n_1\}$，令 $g(2)=f(n_2)$。

以此类推，对于 $g(k)=f(n_k)$，由于 $A$ 是无限集，所以总存在 $n_{k+1}=\min \{n\in \mathbb{N}^+:f(n)\in A,n>n_k\}$，令 $g(k+1)=f(n_{k+1})$。

这样就得到了 $g:\mathbb{N}^+\to A$ 的映射。

(a) 如果 $B_2$ 是无限集，那么由 $1.4.7.$ 可知，$B_2$ 是可数集，那么存在两个双射 $f,g$，有 $f:\mathbb{N}^+\to A_1$，$g:\mathbb{N}^+\to B_2$。现在定义映射 $h:\mathbb{N}^+\to A_1\cup B_2$ 为

$$h(n)=\begin{cases} f\left(\frac{n+1}{2}\right), & n \text{ 为奇数}\\ g\left(\frac{n}{2}\right), & n \text{ 为偶数且不为0}\\ \end{cases}$$

由 $A_1\cap B_2=\varnothing$，可知 $h$ 是单射。由 $f,g$ 的双射性知 $h$ 是满射，于是 $h$ 是双射。这说明 $A_1\cup B_2$ 即 $A_1\cup A_2$ 是可数集。

如果 $B_2$ 是有限集，设它其中的元素个数为 $m$，则 $B_2=\{b_1,b_2,\ldots,b_m\}$。存在双射 $f:\mathbb{N}^+\to A_1$。现在定义映射 $h:\mathbb{N}^+\to A_1\cup B_2$ 为

$$h(n)=\begin{cases} b_n, & n\leq m\\ f(n-m), & n>m\\ \end{cases}$$

同上可得 $h$ 是双射。所以 $A_1\cup B_2$ 即 $A_1\cup A_2$ 是可数集。

(b) 使用数学归纳法。假设 $A_1,A_2,\ldots,A_n$ 是可数集时 $A_1\cup A_2\cup\ldots\cup A_n$ 是可数集，令 $B=A_1\cup A_2\cup\ldots\cup A_n$，则 $A_{n+1}$ 是可数集时 $B\cup A_{n+1}$ 即 $A_1\cup A_2\cup\ldots\cup A_n\cup A_{n+1}$ 也是可数集。又 $n=2$ 时结论成立，由数学归纳法可知结论对 $\forall\ n\in \mathbb{N}^+$ 成立。

由 $1.2.12.(b)$ 可知，有限归纳法不能直接推广到无限的情况。

(c) 二维正整数集为可数集的对角线构造证明法

由图所示，我们可以构造映射 $f:(\mathbb{N^+})^2 \to \mathbb{N^{+}}$，

$$f(m,n)=\begin{cases} 1, &\text{if } m=n=1;\\ f(m+1,n-1)+1, &\text{if } n>1;\\ f(1,m-1)+1, &\text{if } m>1,n=1; \end{cases}$$

$(m,n)$ 是下面这个数表下面第 $m$，右边第 $n$ 个元素：

$$\begin{array}{ccccc} & 1 & 3 & 6 & 10 &\cdots\\ & 2 & 5 & 9 & 14 &\cdots\\ & 4 & 8 & 13 & 19 &\cdots\\ & 7 & 12 & 18 & 25 &\cdots\\ & \vdots & \vdots & \vdots & \vdots \end{array}$$

可以看出，全体正整数都出现在这个表中，且每个正整数只出现一次。所以 $f$ 是一个双射。下面我们严格地证明这一点。

首先，我们证明 $f$ 是单射。 当横纵坐标之和固定时，这些点都在同一对角线上，我们利用这个性质给出下面的证明：

设 $f(m_1,n_1)=f(m_2,n_2)$， 不失一般性，令 $m_1+n_1\leq m_2+n_2$，此时 $(m_1,n_1)$ 所在的对角线在 $(m_2,n_2)$ 所在的对角线的上方（也是左侧）或与之重合。

若不重合即 $m_1+n_1<m_2+n_2$，则 $f(m_1,n_1)\leq f(1,m_1+n_1-1)<f(m_1+n_1,1)$，移动到下一条对角线上，直到 $(m_2,n_2)$ 所在的对角线，即移到 $f(m_1+n_1+k,1)$，其中 $m_1+n_1+k+1=m_2+n_2$。由一条对角线上的单调性，由 $n_2\geq 1$，有 $f(m_2,n_2)\geq f(m_1+n_1+k,1)>f(m_1,n_1)$。这就矛盾。

所以 $m_1+n_1=m_2+n_2$，即 $(m_1,n_1)$ 和 $(m_2,n_2)$ 在同一条对角线上。由对角线上的单调性，$m_1\geq m_2$ 可推出 $f(m_1,n_1)\leq f(m_2,n_2)$，所以 $m_1=m_2$，进而 $n_1=n_2$。综上所述，$f$ 是单射。

接着证明 $f$ 是满射，使用数学归纳法。假设对某个 $k\in \mathbb{N^+}$，$\exists\ m,n\in \mathbb{N^+}$，使得 $f(m,n)=k$，则对 $k+1$，有

$$\begin{matrix} f(m-1,n+1)=f(m,n)+1=k+1, &\text{if } m>1;\\ f(n+1,m)=f(m,n)+1=k+1, &\text{if } m=1; \end{matrix}$$

而 $f(1,1)=1$，所以 $f$ 是满射。

综上所述，$f$ 是双射。

对无穷多个可数集 $A_1,A_2,\ldots$，令 $B_1=A_1$，$B_2=A_2\backslash A_1$，$B_3=A_3\backslash (A_1\cup A_2)$，依此类推，$B_n=A_n\backslash (A_1\cup A_2\cup\ldots\cup A_{n-1})$，则 $A_1,A_2,\ldots$ 的并集可表示为 $B_1\cup B_2\cup B_3\cup\ldots$，且 $B_i\cap B_j=\varnothing$（$i\neq j$）。

若对 $\forall\ i\in \mathbb{N}^+$，$B_i$ 是可数集，设 $B_i=\{b_{i1},b_{i2},\ldots\}$，则定义映射 $g:\mathbb{N}^+\to B_1\cup B_2\cup B_3\cup\ldots$ 为 $f(m,n)\mapsto b_{mn}$，由定义可知 $g$ 是双射，所以 $A_1\cup A_2\cup A_3\cup\ldots$ 是可数集。

若 $\exists\ i\in \mathbb{N}^+$，$B_i$ 是有限集，令 $C$ 为这些有限集的并集，仿照 $1.4.8.(a)$ 中的构造方法，可知 $C$ 是可数集，于是也能得证。

综上， $A_1\cup A_2\cup A_3\cup\ldots$ 是可数集。

附录：$f$ 的通项公式

下面开始推导具体的通项公式。

$f(m,n)$ 的值，亦或说是其序号，是先数完它前面所有的对角线，再数完它所在的对角线的列数。比如说 $f(3,2)=8$，就是因为前面有三条对角线，总共 $6$ 个数，而自己在所在对角线上为第 $2$ 个（也就是第 $2$ 列），所以总共正好是 $6+2=8$。

每条对角线上，行数与列数的和都是相等的。所以 $f(m,n)$ 前的对角线就是从和为 $2$ 到和为 $m+n-1$ 的对角线，总共 $m+n-2$ 条。而第 $n$ 条对角线上的数正好有 $n$ 个，所以就变成了等差数列的计算。最后再加上 $f(m,n)$ 所在对角线的前 $n$ 个数字，就有：

$$f(m,n)=\displaystyle\frac{\left(m+n-1\right)\left(m+n-2\right)}{2}+n$$

(a) 由题意，存在双射 $f:A \to B$。则构造 $g:B \to A$ 使得 $g(f(x)) = x$ 对任意 $x \in A$ 成立。由于 $f$ 是双射，$g$ 也是双射。所以 $B \sim A$。

(b) 由题意，存在双射 $f:A \to B$ 和双射 $g:B \to C$。则构造 $h:A \to C$ 使得 $h(x) = g(f(x))$ 对任意 $x \in A$ 成立。由于 $f,g$ 是双射，$h$ 也是双射。所以 $A \sim C$。

将子集按元素和从小到大，元素个数从少到多排列：$\{1\},\{2\},\{3\},\{1,2\},\ldots$，则每个子集都能对应一个唯一的自然数。故所有有限子集的集合可数。

(a) $f:x\mapsto (x,1/2)$。

(b) 构造如下的映射 $g:S\to (0,1)$：令 $x=0.a_1a_2\ldots$，$y=0.b_1b_2\ldots$，则 $g(x,y)=k$，其中 $k=0.a_1b_1a_2b_2\ldots$。

由于每个实数都有唯一的无限小数表示，由此知 $g$ 为满射。

(a) $(\sqrt{2})^2-2=0$，$(\sqrt[3]{2})^3-2=0$。

令 $t=\sqrt{2}+\sqrt{3}$，考虑 $t^2=5+2\sqrt{6}$，则 $(t^2-5)^2-24=0$，展开来得 $t^4-10t^2+1=0$。

所以它们都是代数数。

(b) 令 $B_m$ 为系数满足 $m-1<\displaystyle \sum_{i=0}^{n}|a_i|\leq m$ 的多项式的根的集合。显然满足 $B_m$ 条件的多项式个数有限，每个多项式的根的个数也有限，所以 $B_m$ 是有限集。

所以 $A_n=\displaystyle\bigcup_{m=1}^\infty B_m$ 由 $1.4.8.$ 知是可数集。

(c) 所有代数数的集合为 $\displaystyle\bigcup_{n=1}^\infty A_n$，由 $1.4.8.$ 知是可数集。

超越数集合是不可数的，换句话说，超越数的个数比代数数要多得多。

(a) 因为 $f$ 是单射，所以若 $f(x_1) = f(x_2)=y$，则有 $x_1 = x_2$，这就说明 $f(x)=y$ 的唯一性，因此 $f^{-1}$ 是良定义且单射的。

(b) 如果不存在 $y\in Y$ 使得 $g(y)=x$，那么 $g^{-1}(x)$ 不存在，因此左侧元素数量为 $0$。

同理，如果左侧延伸到某个元素满足上述情况，那么链在该元素截断，左侧元素数量有限。

若对左侧任何一个元素 $x$，$x\in Y$ 时 $f^{-1}(x)$ 存在， $x\in X$ 时 $g^{-1}(x)$ 存在，那么链可以无限延伸下去，左侧元素数量无限。

(c) 如果两条链所有元素都不相同就不相交。

如果两条链有一个元素相同，由 $f,g$ 的单射性可知，该元素左侧和右侧的所有元素都相同，因此两条链完全相同。

(d) 考虑链 $C_x$ 中的一个元素 $y\in Y$。

若 $y\in f(X)$，则链延伸到 $f^{-1}(y)$，否则链在 $y$ 截断，$C_x\subseteq B$。

若链在 $f^{-1}(y)$ 截断，那么对链中任意的 $x\in Y$ 都有 $x\in f(X)$，$C_x\subseteq A$。

如果继续往左延伸到某个元素 $x$ 使得 $f^{-1}(x)$ 不存在，那么 $C_x\subseteq B$。

如果一直无限延伸，$C_x\subseteq A$。

所以所有 $C_x\subseteq B$ 都以 $y\notin f(X)$ 为头开始。

(e) 根据 (c) 可知，所有链 $C_x$ 互不相交，于是 $f$ 将 $X_1$ 映到 $Y_1$，$g$ 将 $Y_2$ 映到 $X_2$。

又由题意，$X_1\cup X_2=X$，$Y_1\cup Y_2=Y$，根据 $f:X_1\to Y_1$ 和 $g:Y_2\to X_2$ 的双射性，构造如下的映射 $h:X\to Y$：

$$h=\begin{cases} f(x), & x\in X_1,\\ g^{-1}(x), & x\in X_2. \end{cases}$$

显然 $h$ 是双射。所以 $X\sim Y$。

---

习题 1.5 Cantor 定理

Cantor 在无限集理论中的工作远远超出了定理~定理1.4.11的结论。尽管最初遭到抵制，他在这一领域的创造性和不懈努力最终引发了集合论的一场革命，并改变了数学家对无限的理解方式。

Cantor 的对角线方法

定理~定理1.4.11 (1.4.4)的证明与 Cantor 为这一结果提供的任何论证都不同。之所以选择这个证明，是因为它直接揭示了不可数性与完备性概念之间的联系，并且因为使用嵌套区间的技术将在我们后续的工作中多次使用。

Cantor 最初在1874年发表了 $\mathbb{R}$ 不可数的发现，但在1891年，他提供了另一个证明，其简洁性令人惊讶。这个证明依赖于实数的十进制表示，我们将不加任何正式定义地接受并使用它。

开区间 $\left( {0,1}\right) = \{ x \in \mathbb{R} : 0 < x < 1\}$ 是不可数的。

$\Rightarrow)$ 若 $(0,1)$ 不可数，由于可数集的子集可数，所以 $\mathbb{R}$ 也不可数。

$\Leftarrow)$ 若 $\mathbb{R}$ 不可数，假设 $(0,1)$ 可数，则 $[0,1)$ 同样可数，由于 $f:[0,1)\to [1,2)$，$f(x)=x+1$ 是一个双射，所以 $[1,2)$ 可数，同样对 $\forall\ x\in \mathbb{Z}$，$[x,x+1)$ 可数，所以 $\mathbb{R}=\displaystyle \bigcup_{x\in \mathbb{Z}}[x,x+1)$ 可数，矛盾。

故 $(0,1)$ 不可数。

---

与定理~定理1.4.11类似，我们采用反证法，假设确实存在一个函数 $f : \mathbb{N} \rightarrow \left( {0,1}\right)$ ，它是单射且满射的。对于每个 $m \in \mathbb{N}$ ， $f\left( m\right)$ 是一个介于$0$和$1$之间的实数，我们使用十进制表示法来表示它。

$$f\left( m\right) = \cdot {a}_{m1}{a}_{m2}{a}_{m3}{a}_{m4}{a}_{m5}\ldots$$

这里的意思是，对于每个 $m,n \in \mathbb{N},{a}_{mn}$ 是来自集合 $\{ 0,1,2,\ldots ,9\}$ 的数字，表示 $f\left( m\right)$ 的十进制展开中的第 $n$ 位数字。 $\mathbb{N}$ 与$(0,1)$之间的一一对应关系可以用这样的双索引数组来表示。

此处需在原文件中插入图片

关于这一对应的关键假设是，假设$(0,1)$区间内的每一个实数都会出现在列表中的某个位置。

现在进入论证的核心部分。定义一个实数 $x \in \left( {0,1}\right)$ ，其小数展开 $x = {b}_{1}{b}_{2}{b}_{3}{b}_{4}\ldots$ 遵循以下规则

$${b}_{n} = \begin{cases} 2 & {a}_{nn} \neq 2 \\ 3 & {a}_{nn} = 2. \end{cases}$$

让我们明确这一点。为了计算数字 ${b}_{1}$ ，我们查看数组左上角的数字 ${a}_{11}$ 。如果 ${a}_{11} = 2$ ，则选择 ${b}_{1} = 3$ ；否则，设定 ${b}_{1} = 2$ 。

(b) 对 $\forall\ x\in \mathbb{N}$，$b_n\neq a_{nn}$，所以 $x\neq f(n)$。

(c) 由 (b) 可知这样的列表无法覆盖整个 $(0,1)$，所以 $(0,1)$ 不可数。

---

(a) 表中的小数都是实数，各位数都可以随意列出。如果换成有理数：(1) 表中的小数无法任意排布；(2) 得到的表格外面的数不一定是有理数。因此无法用对角线法证明有理数不可数。

(b) 将所有有限小数都写成它的无限小数形式即可规避该问题。

---

假设 $S$ 可数，则可以使用对角线法构造一个如下的表格：

$$\begin{matrix} &1\longleftrightarrow (a_{11},a_{12},a_{13},\ldots)\\ &2\longleftrightarrow (a_{21},a_{22},a_{23},\ldots)\\ &3\longleftrightarrow (a_{31},a_{32},a_{33},\ldots)\\ &\vdots\\ &d\longleftrightarrow (a_{d1},a_{d2},a_{d3},\ldots)\\ &\vdots \end{matrix}$$

然后构造一个新的序列 $(b_1,b_2,b_3,\ldots)$，其中 $b_i\neq a_{ii}$，则该序列不在表格中，矛盾。

故 $S$ 不可数。

---

在区分了可数无穷( $\mathbb{N}$ )和不可数无穷( $\mathbb{R}$ )之后，Cantor 面临的一个新问题是，是否存在一种“高于” $\mathbb{R}$ 的无穷。这在逻辑上是一个危险的领域。我们在定义“具有相同基数”的关系时所给予的同样谨慎，也需要用于定义诸如“基数大于”或“基数小于或等于”的关系。然而，即使不陷入形式定义的泥潭，从下一个结果中我们可以非常清楚地感受到，存在一个超越 $\mathbb{R}$ 连续统的无穷集合的层级结构。

幂集与 Cantor 定理

给定一个集合 $A$ ，幂集 $P\left( A\right)$ 指的是 $A$ 的所有子集的集合。注意， $P\left( A\right)$ 本身被视为一个集合，其元素是 $A$ 的不同可能子集。

(a) $\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}$。

(b) 对于 $A$ 的任意子集，都可以用一个 $0-1$ 序列来表示，$1$ 表示该位置的元素在子集中，$0$ 表示不在。因此列出后可得到 $2^n$ 个子集。

---

(a) $A\to P(A)$：(1) $a\mapsto \{a\}$，(2) $a\mapsto \varnothing$。

(b) $B\to P(B)$：$b\mapsto \{b\}$。

因为 P(A) 中的元素个数远大于 A 中的元素个数，所以不可能有一个满射。

---

解释为什么在(a)和(b)部分中，不可能构造出满射映射。

Cantor 定理指出，练习1.5.6中的现象不仅适用于有限集，也适用于无限集。尽管将 $A$ 映射到 $P\left( A\right)$ 相当容易，但找到一个满射映射是不可能的。

给定任何集合 $A$ ，不存在一个满射函数 $f : A \rightarrow P\left( A\right)$ 。

与同类证明一样，此证明采用间接法。反设 $f : A \rightarrow P\left( A\right)$ 是满射的，以期引出矛盾。与通常我们处理数字集合作为定义域和值域的情况不同， $f$ 是一个集合与其幂集之间的对应关系。对于每个元素 $a \in A,f\left( a\right)$ ，它是 $A$ 的一个特定子集。假设 $f$ 是满射的，意味着 $A$ 的每一个子集都作为 $f\left( a\right)$ 出现，对应于某个 $a \in A$ 。为了引出矛盾，我们将构造一个子集 $B \subseteq A$ ，它不等于任何 $a \in A$ 对应的 $f\left( a\right)$ 。

按照以下规则构造 $B$ 。对于每个元素 $a \in A$ ，考虑子集 $f\left( a\right)$ 。这个 $A$ 的子集可能包含元素 $a$ ，也可能不包含。这取决于函数 $f$ 。如果 $f\left( a\right)$ 不包含 $a$ ，那么我们将 $a$ 包含在我们的集合 $B$ 中。更准确地说，设

$$B = \{ a \in A : a \notin f\left( a\right) \} .$$

采用 $A\to P(A)$：(1) $a\mapsto \{a\}$ 的规则，得到 $B=\varnothing$。

---

我们现在关注一般性论证。由于我们假设函数 $f : A \rightarrow P\left( A\right)$ 是满射的，因此对于某个 ${a}^{\prime } \in A$ ，必须有 $B = f\left( {a}^{\prime }\right)$ 。当我们考虑 ${a}^{\prime }$ 是否是 $B$ 的元素时，矛盾就出现了。

(a) 若 $a'\in B$，则 $a'\notin f(a')$，但 $B=f(a')$，矛盾。

(b) 若 $a'\notin B$，则 $a'\in f(a')$，但 $B=f(a')$，矛盾。

所以从 $A$ 到 $P(A)$ 不存在一个满射函数。

---

(a) 建立 $f:\{0,1\}\to \mathbb{N^+}$: $f(0)=a,f(1)=b$，把所有这样的函数组成集合 $A$ 。我们再建立 $g:A\to \mathbb{(N^+)^2}$: $g(f)=(a,b)$。显然，$g$ 是一个双射。由前述构造，$\mathbb{N}\sim \mathbb{(N^+)^2}$，所以集合 $A$ 可数。

(b) 同上，建立 $f:\mathbb{N^+}\to \{0,1\}$，这个 $f$ 把正整数序列转换成了无穷的 $0-1$ 序列，由 $1.5.4.$ 可知这样的序列不可数，所以全体 $f$ 组成的集合不可数。

(c) 这里借鉴了别人的解答。

设 $p_m$ 是第 $m$ 个素数。我们利用素数的唯一分解性来构造一个映射：

$$\Phi:P(\mathbb{N^+})\setminus\left\{\varnothing,\mathbb{N^+}\right\} \to P(\mathbb{N^+}):\\ \Phi\left(X\right)=\left\{p_m^n: m\in X,n\notin X\right\}$$

记 $\mathcal{A}=\left\{\Phi(X): X\in P(\mathbb{N}^+)\setminus\left\{\varnothing,\mathbb{N}^+\right\}\right\}$，下面我们要证明 $\mathcal{A}$ 是一个不可数的反链，即对任意 $X\neq Y$，都有 $\Phi(X)\not\subseteq \Phi(Y)$ 且 $\Phi(Y)\not\subseteq \Phi(X)$。

首先，由素数的唯一分解性，$\Phi$ 是一个单射。

不妨设 $\exists\ m\in X$，$m\notin Y$（即 $X \not\subseteq Y$），则对某个 $n\notin X$，$p_m^n\in \Phi(X)$，但 $p_m^n\notin \Phi(Y)$（因为底数 $m \notin Y$），所以 $\Phi(X)\not\subseteq \Phi(Y)$。

对于反方向 $\Phi(Y) \not\subseteq \Phi(X)$：
如果 $\exists\ l\in Y$，$l\notin X$（即 $Y \not\subseteq X$），则同理可证 $\Phi(Y)\not\subseteq \Phi(X)$。
如果对 $\forall\ l\in Y$，$l\in X$（即 $Y \subsetneq X$），则对上述 $m$（满足 $m \in X \setminus Y$），任取 $l \in Y$，考察元素 $z = p_l^m$。
$z \in \Phi(Y)$（因底数 $l \in Y$，指数 $m \notin Y$）。
但 $z \notin \Phi(X)$（因指数 $m \in X$，不满足 $\Phi(X)$ 的定义要求）。
所以 $\Phi(Y)\not\subseteq \Phi(X)$。

综上，$\mathcal{A}$ 中任何元素都不是其他元素的子集。又因为 $P(\mathbb{N^+})\setminus\left\{\varnothing,\mathbb{N^+}\right\}$ 是不可数的，所以 $\mathcal{A}$ 也是不可数的。

所以，$\mathcal{A}$ 就是一个不可数的反链。

---

习题 1.6 结语

具有相同基数的关系是一种等价关系(参见练习1.4.9)，大致意味着宇宙中的所有集合可以根据它们的大小组织成不相交的组。两个集合出现在同一个组或等价类中，当且仅当它们具有相同的基数。因此， $\mathbb{N},\mathbb{Z}$ 和 $\mathbb{Q}$ 与所有其他可数集合一起被分在同一类中，而 $\mathbb{R}$ 则在另一个类中，该类包括区间$(0,1)$以及其他不可数集合。Cantor定理的一个含义是， $P\left( \mathbb{R}\right)$ —— $\mathbb{R}$ 的所有子集的集合——与 $\mathbb{R}$ 不在同一类中，而且没有理由在此停止。 $P\left( \mathbb{R}\right)$ 的子集集合——即 $P\left( {P\left( \mathbb{R}\right) }\right)$ ——又在另一个类中，这个过程无限延续。

将集合的宇宙划分为不相交的组后，为每个集合附加一个“数字”将非常方便，这个数字可以像自然数一样用来表示有限集的大小。给定一个集合 $X$ ，存在一个称为 $X$ 的基数(cardinal number)的东西，记作card $X$ ，它的行为非常符合这种模式。例如，两个集合 $X$ 和 $Y$ 满足 $\operatorname{card}X = \operatorname{card}Y$ 当且仅当 $X \sim Y$ 。(严格定义card $X$ 需要一些重要的集合论知识。一种方法是定义card $X$ 为一个非常特定的集合，该集合总是可以在与 $X$ 相同的等价类中唯一找到。)

回顾 Cantor 定理，我们强烈地感觉到，无穷集合的大小存在一种顺序，这种顺序应该在我们新的基数系统中得到体现。具体来说，如果能够以一一对应的方式将集合 $X$ 映射到 $Y$ 中，那么我们希望 $\operatorname{card}X \leq \operatorname{card}Y$ 。写成严格不等式 $\operatorname{card}X < \operatorname{card}Y$ 应该表明，可以将 $X$ 映射到 $Y$ 中，但无法证明 $X \sim Y$ 。用这种符号重新表述，Cantor定理指出，对于每个集合 $A$ ，有基数 $A < \operatorname{card}P\left( A\right)$ 。

有一些重要的细节需要解决。当我们意识到 Cantor 定理的一个含义是不存在“最大”集合时，一种形而上学的问题便出现了。诸如“设 $U$ 为所有可能事物的集合”这样的声明是自相矛盾的，因为我们立即得到 $\operatorname{card}U < \operatorname{card}P\left( U\right)$ ，因此集合 $U$ 并不包含它声称要包含的所有内容。这类问题最终通过施加一些限制条件来解决，即规定什么才能算作一个集合。随着集合论的形式化，公理必须精心设计，以确保像 $U$ 这样的对象根本不被允许。一个更实际且需要关注的问题是证明我们对基数之间“ $\leq$ ”的定义确实是一个序关系。这涉及到证明基数具有类似于实数的性质，即如果 $\operatorname{card}X \leq \operatorname{card}Y$ 且 $\operatorname{card}Y \leq \operatorname{card}X$ ，则 $\operatorname{card}X = \operatorname{card}Y$ 。最终，这归结为证明如果存在 $f : X \rightarrow Y$ 是单射，且存在 $g : Y \rightarrow X$ 是单射，那么可以找到一个既是单射又是满射的函数 $h : X \rightarrow Y$ 。Cantor未能证明这一事实，但最终由 Ernst Schröder (1896年)和 Felix Bernstein (1898年)独立提供。Schröder-Bernstein 定理的论证在练习1.4.13中概述。

Cantor 所关注的、源自新兴基数理论的另一个深层次问题，在他有生之年并未得到解决。由于可数集的重要性，符号 ${\aleph }_{0}$ 常被用来表示基数 $\mathbb{N}$ 。当我们记住可数集是最小的无限集类型时，下标“0”是合适的。就基数而言，如果基数 $X < {\aleph }_{0}$ ，那么 $X$ 是有限的。因此， ${\aleph }_{0}$ 是最小的无限基数。 $\mathbb{R}$ 的基数也足够重要，值得特别命名为 $\aleph_1 = \operatorname{card}\mathbb{R} = \operatorname{card}\left( {0,1}\right)$ 。定理~定理1.4.11 和 定理1.5.1的内容是 ${\aleph }_{0} < \aleph_1$ 。困扰Cantor的问题是，是否存在严格介于这两者之间的基数。换句话说，是否存在一个集合 $A \subseteq \mathbb{R}$ ，使得 $\operatorname{card}\mathbb{N} < \operatorname{card}A < \operatorname{card}\mathbb{R}$ ？Cantor认为这样的集合不存在。在基数的排序中，他推测 $\aleph_1$ 是 ${\aleph }_{0}$ 的直接后继。

Cantor 的“连续统假设”是过去一个世纪中最著名的数学难题之一。它的意外解决分为两部分。1940年，德国逻辑学家和数学家 Kurt Gödel 证明，仅使用集合论中公认的公理集，无法否定连续统假设。1963年，Paul Cohen 成功证明，在相同的规则下，也无法证明这一猜想。综合来看，这两项发现意味着连续统假设是不可判定的。它可以被接受或拒绝作为关于无限集性质的陈述，无论哪种情况都不会产生任何逻辑矛盾。

提到 Kurt Gödel，不禁让人对 Cantor 工作的意义作最后的评论。Gödel 以其“不完备性定理”最为著名，这些定理涉及一般公理系统的强度。Gödel 所证明的是，任何为研究算术而创建的一致公理系统必然注定是“不完备的”，即总会存在一些命题，使公理系统因过于薄弱而无法证明。在 Gödel 极其复杂的证明的核心，有一种与定理_{定理1.5.1和}定理1.5.2证明中发生的事情密切相关的操作类型。Cantor 证明方法的变体也可以在计算机科学的限制性结果中找到。“停机问题”大致询问是否存在某种通用算法，可以查看每个程序并决定该程序是否最终终止。证明这种算法不存在的核心论证使用了对角线化类型的构造。主要观点是，不仅Cantor定理的推论深远，其论证技术也同样重要。作为这一现象的一个更直接的例子，对角线化方法在第6章中再次被使用——以一种建设性的方式——作为 Arzela-Ascoli 定理证明的关键步骤。

---